package com.primary.linkedList;

import java.util.List;
import java.util.Stack;

/**
 * @author: yyh
 * @description:反转链表：https://leetcode.cn/leetbook/read/top-interview-questions-easy/xnnhm6/
 * @date: 2022/7/18 22:06
 */
public class ReverseList {

    /**
     * 给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
     *
     * 进阶：链表可以选用迭代或递归方式完成反转。你能否用两种方法解决这道题？
     */


    public static void main(String[] args) {
        ListNode c = new ListNode(4);
        ListNode b = new ListNode(3,c);
        ListNode a = new ListNode(2, b);
        ListNode head = new ListNode(1,a);

//        reverseList(head);
//        reverseList_1(head);
        reverseList_2(head);
    }

    public static ListNode reverseList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        Stack<ListNode> stack = new Stack();
        while (head != null) {
            ListNode next = head.next;
            head.next = null;
            stack.push(head);
            head = next;
        }
        head = stack.pop();
        ListNode newListNode = head;
        while (!stack.empty()) {
            ListNode newNext = stack.pop();
            newListNode.next = newNext;
            newListNode = newNext;
        }
        return head;
    }

    public static ListNode reverseList_1(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        Stack<ListNode> stack = new Stack();
        while (head != null) {
            stack.push(head);
            head = head.next;
        }
        head = stack.pop();
        ListNode newListNode = head;
        while (!stack.empty()) {
            ListNode newNext = stack.pop();
            newListNode.next = newNext;
            newListNode = newNext;
        }
        newListNode.next = null;
        return head;
    }

    public static ListNode reverseList_2(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode next = head.next;
        //递归到尾节点，递归退出时则为反转的顺序
        ListNode reverse = reverseList_2(next);

        next.next = head;
        head.next = null;
        return reverse;
    }

    public static class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }
}
